package com.kevinkk.backtracking;

import java.util.ArrayList;
import java.util.List;

/**
 * 给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
 * 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
 *
 * 子集问题的不区别在于 将 path 加入 res 时没有任何条件
 */

public class Subsets {
    class Solution {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();

        public List<List<Integer>> subsets(int[] nums) {
            backtracking(nums, 0);
            return res;
        }

        private void backtracking(int[] nums, int startIndex){
            res.add(new ArrayList<>(path));

            for(int i = startIndex; i < nums.length; i++){
                path.add(nums[i]);
                backtracking(nums, i+1);
                path.remove(path.size()-1);
            }
        }
    }
}
